競プロ日記

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 29;
constexpr lint   INFL = 1LL << 61;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

template 
class ModInt {
  long long n_;

  public:
  constexpr ModInt(const long long num = 0) : n_(num % mod_num) {}
  constexpr const long long&value() const { return n_; }
  constexpr bool   operator==(const ModInt &r) const { return this->n_ == r.n_; }
  constexpr bool   operator==(const long long &r) const { return this->n_ == r; }
  constexpr bool   operator!=(const ModInt &r) const { return this->n_ != r.n_; }
  constexpr bool   operator!=(const long long &r) const { return this->n_ != r; }
  constexpr bool   operator<(const ModInt &r) const { return this->n_ < r.n_; }
  constexpr bool   operator<(const long long &r) const { return this->n_ < r; }
  constexpr bool   operator>(const ModInt &r) const { return this->n_ > r.n_; }
  constexpr bool   operator>(const long long &r) const { return this->n_ > r; }
  constexpr bool   operator<=(const ModInt &r) const { return this->n_ <= r.n_; }
  constexpr bool   operator<=(const long long &r) const { return this->n_ <= r; }
  constexpr bool   operator>=(const ModInt &r) const { return this->n_ >= r.n_; }
  constexpr bool   operator>=(const long long &r) const { return this->n_ >= r; }
  constexpr ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }
  constexpr ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }
  constexpr ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }
  constexpr ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }
  constexpr ModInt operator+(const long long &r) const { return ModInt(*this) += ModInt(r); }
  constexpr ModInt operator-(const long long &r) const { return ModInt(*this) -= ModInt(r); }
  constexpr ModInt operator*(const long long &r) const { return ModInt(*this) *= ModInt(r); }
  constexpr ModInt operator/(const long long &r) const { return ModInt(*this) /= ModInt(r); }
  friend ModInt operator+(const long long &l, const ModInt &r) { return ModInt(l) += r; }
  friend ModInt operator-(const long long &l, const ModInt &r) { return ModInt(l) -= r; }
  friend ModInt operator*(const long long &l, const ModInt &r) { return ModInt(l) *= r; }
  friend ModInt operator/(const long long &l, const ModInt &r) { return ModInt(l) /= r; }
  constexpr ModInt &operator++() { return *this += 1; }
  constexpr ModInt &operator--() { return *this -= 1; }
  constexpr ModInt &operator+=(const ModInt &r) {
    n_ += r.n_;
    if (n_ >= mod_num) n_ -= mod_num;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &r) {
    if (n_ < r.n_) n_ += mod_num;
    n_ -= r.n_;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &r) {
    n_ = n_ * r.n_ % mod_num;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt r) {
    long long exp = mod_num - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r   *= r;
      exp /= 2;
    }
    return *this;
  }
  friend istream &operator>>(istream &is, ModInt<mod_num> &r) {
    is >> r.n_;
    r.n_ %= r.mod_num;
    return is;
  }
  friend ostream &operator<<(ostream &os, const ModInt<mod_num> &r) { return os << r.n_; }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
};

bool check(const lint n, const int dig) { return n & (1LL << (59 - dig)); }

using mint = ModInt;
int main(void) {
  lint l, r;
  cin >> l >> r;
  vector<vector<vector<vector>>> dp(61, vector<vector<vector>>(2, vector<vector>(2, vector(2))));
  // 60桁目(0-index)以上が1の数は必ずRより大きくなってしまうので0のみから成る1通りのみ
  dp[0][0][0][0] = 1;
  rep (d, 60) {
    bool cl = check(l, d), cr = check(r, d);
    rep (i, 2) {
      rep (j, 2) {
        rep (k, 2) {
          auto val = dp[d][i][j][k];
          rep (x, 2) {
            rep (y, 2) {
              // 条件に当てはまるかチェック
              // xの方が大きい
              if (x && !y) continue;
              // 最上位ビットが異なる
              if (!k && (x ^ y)) continue;
              // L以上が未確定な状態でLよりも小さい
              if (!i && cl && (!x || !y)) continue;
              // R以下が未確定な状態でRよりも大きい
              if (!j && !cr && (x || y)) continue;
              //
              // 遷移先が変わるかチェック
              int ni = i, nj = j, nk = k;
              // L以上が確定
              if (!cl && x) ni = 1;
              // R以下が確定
              if (cr && !y) nj = 1;
              // 最上位ビットが確定
              if (!k && x) nk = 1;
              //
              // 遷移
              dp[d + 1][ni][nj][nk] += val;
            }
          }
        }
      }
    }
  }
  mint ans = 0;
  rep (i, 2) {
    rep (j, 2) {
      rep (k, 2) {
        ans += dp[60][i][j][k];
      }
    }
  }
  cout << ans << endl;
  return 0;
}

過去最高に混乱したDP。
分からなさすぎて珍しくコードにコメントを書いた。
分からなかったのは遷移条件ではなく遷移方法(DPの値全てに(x,y)の値を持って遷移すること)なのだが、1から記録していかないとつらいと感じてコメントを残すことにした。
解法も当然のごとく思いつなかったのだが、解法を見た後でも自力で実装できなかった。
添字4つの時点で初体験なのに、それに加えて別途遷移先を判断する数が必要とは。
各所で「2つの数字を管理する」というようなことが書かれていたが、なるほどこういうことかと実装できて初めて意味を理解する。
確かにこのDPで遷移先を全て網羅できている。
網羅できていることは分かるし、遷移条件も分かる。
だが、全体として見ると自然に捉えられないなぁという感想。
経験が足りない分余計な思考が入ってしまうので、それら全てに間違っているという判断を下しながら、全体を結合して考えても合っていると判断するには脳のメモリが足りない。
最近ますますDP is 経験を認識してきた。

最初考えたのが、(x,y)の値を持つのではなく、以下のように何回足し合わせられるか、というような遷移である。
dp[d][0][0][0] = dp[d+1][0][0][0] * A + dp[d+1][0][0][1] * B + ...
dp[d][1][0][0] = dp[d+1][0][0][0] * X + dp[d+1][0][0][1] * Y + ...
確かにこれでもできそうだが、(x,y)それぞれについて考えてこの遷移量なので、この方針だとさらにややこしいことになりそう・・・。
そもそもこの方針を思いついたのは、「DPは余計にループせずに全遷移を網羅するもの」という考えで組もうとしているから。
確かにループの数は小さくなるのだが、結局四則演算の数はあまり変わらなさそうなので全体としてもあまり変わらないかもしれない。
(x, y)の状態が大きかったら変わる？かもしれない？
だとしたら難易度のレベルがいくつか上がりそうなので考えるべきではないと判断することにした。

大事なのは、全ての状態・遷移を網羅できて、なおかつ実行可能時間内に収めること。
余計なこと考えるのはせめて黄色くらいになってからにしようと思い直した。
余計なことではないだろうが、慣れていない種類の難しい問題の詳細はそりゃ相当難しい。